UVa/11096 - Nails/p11096.cpp

   1
   2 #include <iostream>
   3 #include <algorithm>
   4 #include <vector>
   5 #include <math.h>
   6
   7 using namespace std;
   8
   9 struct Point{
  10   long long x, y;
  11   bool operator < (const Point &p) const {
  12     return (x < p.x || (x == p.x &&y < p.y));
  13   }
  14 };
  15
  16 // 2D cross product.
  17 // Return a positive value, if OAB makes a counter-clockwise turn,
  18 // negative for clockwise turn, and zero if the points are collinear.
  19 long long cross(const Point &O, const Point &A, const Point &B)
  20 {
  21         return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  22 }
  23
  24 // Returns a list of points on the convex hull in counter-clockwise order.
  25 // Note: the last point in the returned list is the same as the first one.
  26 vector<Point> convexHull(vector<Point> P)
  27 {
  28         long long n = P.size(), k = 0;
  29         vector<Point> H(2*n);
  30
  31         // Sort Points lexicographically
  32         sort(P.begin(), P.end());
  33
  34         // Build lower hull
  35         for (long long i = 0; i < n; i++) {
  36                 while (k >= 2 && cross(H[k-2], H[k-1], P[i]) < 0) k--;
  37                 H[k++] = P[i];
  38         }
  39
  40         // Build upper hull
  41         for (long long i = n-2, t = k+1; i >= 0; i--) {
  42                 while (k >= t && cross(H[k-2], H[k-1], P[i]) < 0) k--;
  43                 H[k++] = P[i];
  44         }
  45
  46         H.resize(k);
  47         return H;
  48 }
  49
  50 void printPnt(const Point &p){
  51   cout << "(" << p.x << "," << p.y << ")";
  52 }
  53
  54 int main(){
  55   long long n;
  56   cin >> n;
  57   while (n--){
  58     //procesar caso
  59     long long ilen, nails;
  60     cin >> ilen >> nails;
  61     vector<Point> g(nails);
  62
  63     for (long long i=0; i<nails; ++i){
  64       long long x, y;
  65       cin >> x >> y;
  66       g[i].x = x;
  67       g[i].y = y;
  68     }
  69
  70     vector<Point> chull = convexHull(g);
  71     /*for (int i=0; i<chull.size(); i++){
  72       printPnt(chull[i]); cout << " ";
  73     }
  74     cout << endl;*/
  75     if (chull.size() > 1){
  76       long double dlen = (long double)ilen;
  77       long double dist = 0.0;
  78       for (int i=0; i<chull.size()-1; i++){
  79         //Euclidean distance
  80         //cout << "dist "<<i<<" es: " << dist <<endl;
  81         dist += (long double)sqrt((chull[i].x-chull[i+1].x)*(chull[i].x-chull[i+1].x)+(chull[i].y-chull[i+1].y)*(chull[i].y-chull[i+1].y));
  82       }
  83       //cout << "dist es: " << dist << endl;
  84       if (dlen > dist){
  85         cout << ilen << ".00000\n";
  86       }else{
  87         printf("%.5Lf\n", dist);
  88       }
  89
  90     }else{ //solo hay un clavo
  91       cout << ilen << ".00000\n";
  92     }
  93   }
  94   return 0;
  95 }